<?php

// Algo that searches for the longest common substring of two strings

$string1 = <<< EOD
Facebook is an online social networking service, whose name stems from the colloquial name for the book given to students at the start of the academic year by some university administrations in the United States to help students get to know each other
EOD;

$string2 = <<< EOD
a
EOD;

//$string1 = "banana";
//$string2 = "banalyze";

echo "String 1:<br/>$string1<br/>";
echo "String 2:<br/>$string2<br/>";

echo "Common string:".longestCommonSubstring($string1, $string2);


function longestCommonSubstring( $string1, $string2 ){
	$length1 = strlen( $string1 );
	$length2 = strlen( $string2 );
	if( 0 >= $length1 || 0 >= $length2 ){
		// Either string is empty
		return "";
	}

	// Init a 2D array
	$counts = array_fill( 0, $length1, array_fill(0, $length2, 0) );

	// Locator for the substring
	$sub_length = 0;
	$sub_index1 = 0;

	// Loop through
	for( $index1=0; $index1<$length1; $index1++ ){
		for( $index2=0; $index2<$length2; $index2++ ){
			// When this char is a match
			if( $string1[$index1] == $string2[$index2] ){
				if( 0 == $index1 || 0 == $index2 ){
					// Begining of either string
					$counts[$index1][$index2] = 1;
				}
				else {
					// Increment the count from previous match
					$counts[$index1][$index2] = $counts[$index1 - 1][$index2 - 1] + 1;
				}

				// Update the longest
				if( $counts[$index1][$index2] > $sub_length ){
					$sub_index1 = $index1;
					$sub_length = $counts[$index1][$index2];
				}

			}
		}
	}

	/*
	// Print the matrix
	for( $index1=0; $index1<$length1; $index1++ ){
		for( $index2=0; $index2<$length2; $index2++ ){
			echo "{$counts[$index1][$index2]}   ";
		}
		echo "<br/>";
	}
	*/

	echo "Longest common substring length is $sub_length<br/>";
	echo "Longest common substring ends in string1 at $sub_index1<br/>";

	return substr($string1, $sub_index1-$sub_length+1, $sub_length);
}